package LeetCode刷题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-30 15:25
 * @description: Functions of this class is
 *
 * 官方解法：
 *class Solution {
 *     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 *         List<List<Integer>> ans = new LinkedList<List<Integer>>();
 *         if (root == null) {
 *             return ans;
 *         }
 *
 *         Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
 *         nodeQueue.offer(root);
 *         boolean isOrderLeft = true;
 *
 *         while (!nodeQueue.isEmpty()) {
 *             Deque<Integer> levelList = new LinkedList<Integer>();
 *             int size = nodeQueue.size();
 *             for (int i = 0; i < size; ++i) {
 *                 TreeNode curNode = nodeQueue.poll();
 *                 if (isOrderLeft) {
 *                     levelList.offerLast(curNode.val);
 *                 } else {
 *                     levelList.offerFirst(curNode.val);
 *                 }
 *                 if (curNode.left != null) {
 *                     nodeQueue.offer(curNode.left);
 *                 }
 *                 if (curNode.right != null) {
 *                     nodeQueue.offer(curNode.right);
 *                 }
 *             }
 *             ans.add(new LinkedList<Integer>(levelList));
 *             isOrderLeft = !isOrderLeft;
 *         }
 *
 *         return ans;
 *     }
 * }
 **/
public class No二叉树的锯齿形层序遍历 {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public static void main(String args[]){

    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans=new ArrayList();
        if(root!=null){
            LinkedList<TreeNode> queue=new LinkedList();
            queue.add(root);
            boolean leftStart=true;//设置一个变量，记录当前的遍历顺序
            while(!queue.isEmpty()){
                List<Integer> sub=new ArrayList();
                int size=queue.size();
                if(leftStart){//从左往右
                    for(int i=0;i<size;i++){
                        TreeNode p=queue.pop();
                        sub.add(p.val);
                        if(p.left!=null){
                            queue.add(p.left);
                        }
                        if(p.right!=null){
                            queue.add(p.right);
                        }
                    }
                }
                else{//从右往左
                    LinkedList<Integer> stack=new LinkedList();
                    for(int i=0;i<size;i++){
                        TreeNode p=queue.pop();
                        stack.push(p.val);
                        if(p.left!=null){
                            queue.add(p.left);
                        }
                        if(p.right!=null){
                            queue.add(p.right);
                        }
                    }
                    while(!stack.isEmpty()){
                        sub.add(stack.pop());
                    }
                }
                ans.add(sub);
                leftStart=!leftStart;//顺序倒转
            }
        }
        return ans;
    }
}